/*
 * @lc app=leetcode.cn id=31 lang=java
 *
 * [31] 下一个排列
 */

// @lc code=start
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int k = n-1;

        while(k - 1 >= 0 && nums[k] <= nums[k-1]){
            k--;
        }
        if(k == 0) {
            reverse(nums, 0, n-1);
            return;
        } else {
            int j = k;
            while(j + 1 < n && nums[j+1] > nums[k-1]){
                j++;
            }
            swap(nums, k-1, j);
            reverse(nums, k, n-1);
        }
    }

    private void reverse(int[] nums, int start, int end){
        while(start < end){
            swap(nums, start, end);
            start++;
            end--;
        }
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
// @lc code=end

